The present invention relates generally to data communication systems, and specifically to traffic management of subscriber access to a high-speed network.
When a subscriber establishes a data connection to an Asynchronous Transfer Mode (ATM) network, a traffic contract is negotiated between the subscriber and the network specifying, inter alia, rates at which the network will accept data from the subscriber. Within the limits of these rates, the network guarantees that all data transmitted by the subscriber will be accepted and transmitted over the network. When the subscriber exceeds the contract rates, the network is liable to discard the excess data, although it may attempt to transmit the excess data when bandwidth is available.
The algorithm used in ATM networks for controlling transmission rates is known as the Generic Cell Rate Algorithm (GCRA) . GCRA operates, metaphorically, as a leaky bucket, with a fixed leak rate corresponding to a sustainable transmission rate specified by the subscriber""s contract. When the subscriber transmits for a period at a rate that is lower than the sustainable contract rate, the bucket empties out, giving the subscriber the option subsequently of transmitting at a higher rate until the bucket fills up. Sustained transmission above the contract rate, however, will cause the bucket to fill up and overflow, whereupon excess cells are discarded. GCRA is defined formally in recommendation I.371 of the International Telecommunication Union (ITU-T) and in specification AF-TM-0056.00 of the ATM Forum (Traffic Management Specification Version 4.0). A concise definition and description of the algorithm is provided by de Prycker in Chapter 7 of Asynchronous Transfer Mode: Solution for Broadband ISDN (Prentice Hall, London, 1995). All of these documents are incorporated herein by reference.
GCRA specifies three key parameters for controlling subscriber transmission rates: the Peak Cell Rate (PCR), Sustainable Cell Rate (SCR) and Burst Tolerance (xcfx84s). PCR is a mandatory parameter, defined as the inverse of a minimum time T that is allowed between the arrivals of any two consecutive cells at the network interface. If cells are spaced by less than T, there is no guarantee that they will be transmitted. SCR and xcfx84s are optional, and are provided in order to enable the network to allocate resources more efficiently. SCR represents the average, long-term cell rate (less than the PCR) that the network guarantees to support. It corresponds to the leak rate of the bucket mentioned above. The subscriber may transmit data continuously at the SCR. If the subscriber transmits below the SCR for a period of time, however, the subscriber""s xe2x80x9cbucketxe2x80x9d empties out, and it becomes possible for the subscriber to transmit a burst of data at the PCR. The size of the burst that will be accepted by the network depends on how xe2x80x9cemptyxe2x80x9d the bucket is (i.e., how far below the SCR was the subscriber""s transmission rate, and for how long) . In any case, the burst may be no larger than a Maximum Burst Size (MBS), defined by:
xe2x80x83MBS=[1+xcfx84s/(Tsxe2x88x92T)]xe2x80x83xe2x80x83(1)
wherein Ts=1/SCR. The MBS corresponds roughly to the volume of the bucket.
ATM networks carry cells of constant, fixed size. The GCPA is therefore defined in terms of minimum times allowed between cells (T, Ts, and xcfx84s). ATM systems measure these times in order to implement the algorithm. On the other hand, in packet data networks, such as Internet Protocol (IP) networks, the size of the packets is variable. Thus, when subscriber equipment generating variable-size packets is interfaced to a high-speed ATM network, it is necessary to take the packet size and packet rate into account in applying the GCRA. An approach of this sort is used in the Cisco Systems LightStream 2020 multiservice ATM switch. The traffic management properties of this switch are described in a document available at www.cisco.com/univercd/cc/td/doc/product/atm/12020/2020r211/sysover/traffic.htm, which is incorporated herein by reference. The approach adopted by this switch, however, applies only the mandatory PCR to the incoming packets. It does not attempt to deal with the added complication of the optional SCR and MBS parameters.
It is an object of the present invention to provide improved methods and apparatus for network traffic control.
It is a further object of some aspects of the present invention to provide improved methods and apparatus for implementing the GCRA in an ATM network access system that receives packet data for transmission over the network. It is a particular object of such aspects of the present invention to provide methods and apparatus for applying the GCRA using the optional SCR and MBS parameters.
In preferred embodiments of the present invention, an ATM network edge access interface receives data packets from a subscriber for transmission over the ATM network as cells. A contract between the subscriber and the network specifies the PCR, SCR and MBS (or the equivalent times T, xcfx84s and xcfx84s). As long as the data rate of the input packets does not exceed the SCR, the interface converts the packets to ATM cells and transmits them at a rate equal to or less than the SCR. As long as the input packet data rate is below the SCR, the subscriber accrues a xe2x80x9ccreditxe2x80x9d at the network interface, up to a maximum given by the MBS. This credit is used subsequently, if the packet rate exceeds the SCR, to enable the interface to accept a burst of packet data and to transmit the data at the PCR.
The network access interface of the present invention is thus able to transmit packet data over the ATM network at either the PCR or the SCR (or below), making more efficient use of available bandwidth than is afforded by network equipment known in the art. Furthermore, by implementing transmission rate control at the packet level, rather than at the cell level as in systems known in the art, the present invention can help to reduce the computational load due to the rate control algorithm.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a method for controlling data transmission over a network, including:
receiving a succession of data packets from a packet input at a potentially variable input data rate, each packet in the succession potentially having a respective, non-uniform packet size; and
for each of the packets in the succession:
comparing the respective packet size to a transmission credit allocated to the input;
if the allocated credit is sufficient, compared to the respective packet size, transmitting the packet over the network at a peak data transmission rate predetermined by the network; and
if the allocated credit is insufficient, compared to the respective size, transmitting at least a portion of the packet over the network at a rate no greater than a sustainable transmission data rate predetermined by the network, which sustainable transmission rate is less than the peak data transmission rate.
Preferably, transmitting at least a portion of the packet includes, if the allocated credit is insufficient compared to the respective packet size, transmitting the entire packet at the sustainable data transmission rate.
Alternatively, transmitting at least a portion of the packet includes, if the allocated credit is insufficient compared to the respective packet size, transmitting a first portion of the packet at the peak data transmission rate and transmitting a remaining portion of the packet at the sustainable data transmission rate. Preferably, transmitting the first portion comprises transmitting a quantity of the data that is substantially equal to the allocated credit, and reducing the credit substantially to zero after transmitting the quantity of the data that is substantially equal to the allocated credit.
In a preferred embodiment, the network includes an Asynchronous Transfer Mode (ATM) network, and the peak and sustainable data transmission rates respectively correspond to peak and sustainable cell rates. Preferably, receiving the succession of data packets includes receiving the packets over an Ethernet link.
Preferably, the method includes increasing the transmission credit allocated to the input when the variable input rate is less than the sustainable transmission rate. Further preferably, increasing the transmission credit includes finding a time of completion of transmission from the interface of a first one of the packets and a time of arrival at the interface of a second one of the packets, successive to the first packet, and increasing the credit responsive to a difference between the time of completion of transmission of the first packet and the time of arrival of the second packet. Most preferably, finding the time of transmission includes estimating the time of transmission of the first packet responsive to the size of the first packet and the rate of transmission of the first packet. Additionally or alternatively, increasing the transmission credit includes increasing the credit up to a maximum credit that is proportional to a maximum burst size predetermined by the network.
Preferably, transmitting the packet at the peak transmission rate includes reducing the transmission credit allocated to the input by an amount proportional to the packet size.
There is also provided, in accordance with a preferred embodiment of the present invention, apparatus for controlling data transmission over a high-speed network, including:
an input packet interface, configured to receive over a packet link at a variable input rate a succession of packets containing data, each packet in the succession having a respective, non-uniform packet size;
an output interface to the network, configured to transmit the data over the high-speed network at either a peak transmission rate predetermined by the network or at a rate no greater than a sustainable transmission rate predetermined by the network, which sustainable transmission rate is less than the peak transmission rate; and
a processor, coupled between the input and output interfaces and adapted to control the transmission rate of the data contained in each of the data packets in the succession by comparing the respective packet size to an allocated transmission credit, such that if the allocated credit is sufficient, compared to the respective packet size, the packet is transmitted over the network at the peak transmission rate, while if the allocated credit is insufficient, compared to the respective packet size, the packet is transmitted at the rate no greater than the sustainable transmission rate.
The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings in which: